package 力扣日常刷题.木22一月.第09天0117;

/**
 * @author 帅小伙
 * @date 2022/1/17
 * @description 方法一：动态规划
 * 从当前到最后
 * 我们用 dp[i][j] 表示字符串 s1[i:] 和 s2[j:]
 * （s1[i:] 表示字符串 s1 从第 ii 位到末尾的子串，
 * s2[j:] 表示字符串 s2 从第 jj 位到末尾的子串，
 * 字符串下标从 0 开始）达到相等所需删除的字符的 ASCII 值的最小和，最终的答案为 dp[0][0]。
 * 当 s1[i:] 和 s2[j:] 中的某一个字符串为空时，dp[i][j] 的值即为另一个非空字符串的所有字符的 ASCII 值之和
 * 链接：https://leetcode-cn.com/problems/minimum-ascii-delete-sum-for-two-strings/solution/liang-ge-zi-fu-chuan-de-zui-xiao-asciishan-chu-he-/
 */
public class Demo09动态规划中等两个字符串的最小ASCLL删除和 {


    public int minimumDeleteSum(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        int[][] dp = new int[n + 1][m + 1];

        // s2 == null  之后dp[][m] 全都要加上
        for (int i = n - 1; i >= 0; i--) {
            dp[i][m] = dp[i + 1][m] + s1.codePointAt(i);
        }
        for (int i = n - 1; i >= 0; i--){
            dp[n][i] = dp[n][i+1] + s2.codePointAt(i);
        }

        for (int i = n-1; i >=0 ; i--) {
            for (int j = m-1; j >=0 ; j--) {
                if(s1.charAt(i) == s2.charAt(j)){
                    dp[i][j] = dp[i+1][j+1];
                }else{
                    dp[i][j] = Math.min(dp[i][j+1]+s2.codePointAt(j),
                            dp[i+1][j]+s1.codePointAt(i));
                }
            }
        }
        return dp[0][0];
    }
}
